#include <stdio.h>
#include <stdlib.h>

#define INF -1

class Table {
  public:
    Table(int vertexes); //Creates random table
    Table(Table &table, int deleted_vertex); 
      //Deletes deleted_vertex from table and copy
    ~Table() {};
    void Normalize(); 
    void CountAgregateCosts(); 
    //Counts min cost of passing through the graph and writes it to the table
    double GetMissingCost(int start, int finish);
    void Print();
    double GetValue(int i, int j);
    double min(const double x, const double y) {if(x > y) return y; else return x;}
  private:
    double **table;
    int vertexes;
    int size;
};

int main() {
  Table table(5);
//  Table temp(table,1);
  table.CountAgregateCosts();
  table.Normalize();
  table.Print();
  table.GetMissingCost(1,4);
  table.Print();
//  temp.Print();
  return 0;
}

Table::Table(int vertexes) {
  int i,j;
  
  this->size = vertexes+2;
  this->vertexes = vertexes;
  table = (double **)malloc(size*sizeof(double *));
  for(i=0;i<size;++i) 
    table[i] = (double *)malloc(size*sizeof(double));

  for(i=1;i<=vertexes;++i) 
    for(j=1;j<=vertexes;++j)
      table[i][j] = static_cast<double>(rand()%100);

  for(i = 0; i <= vertexes; ++i) {
    table[0][i] = i;
    table[i][0] = i;
    table[i][i] = INF;
  }
}

Table::Table(Table &table, int deleted_vertex) {
  int i,j;
  
  this->size = table.size-1;
  this->vertexes = table.vertexes-1;
  this->table = (double **)malloc(size*sizeof(double *));
  for(i=0;i<size;++i) 
    this->table[i] = (double *)malloc(size*sizeof(double));
  
  //Ignores table[deleted_vertex][*] and table[*][deleted_vertex]:
  for(i = 0; i <= vertexes+1; ++i) {
    if(i == deleted_vertex) continue;   
    for(j=0;j<=vertexes+1;++j) {
      if(j == deleted_vertex) continue;
      this->table[i-(i > deleted_vertex)][j-(j>deleted_vertex)] = 
        table.GetValue(i,j);
    }
  }
}

void Table::Print() {
  int i,j;

  for(i=0;i<size;++i) {
    for(j=0;j<size;++j)
      printf("%.0f\t",table[i][j]);
    printf("\n");
  }
  printf("\n");
}  

double Table::GetValue(int i, int j) {
  if (i < size && j < size && i > 0 && j > 0) return table[i][j];
  else printf("Table::GetValue - wrong bound\n");
  return -2.0;
}

void Table::CountAgregateCosts() {
  int i,j;
  
  table[vertexes+1][vertexes+1] = 0;
  for(i=1;i<=vertexes;++i) {
    //Finding min value in i th string:
    for(j=1;j<=vertexes,table[i][j]==INF;++j) {}; //Finding the number of first value x != INF
    table[i][vertexes+1] = table[i][j]; //x is a start min value
    for(;j<=vertexes;++j) {
      if (table[i][j] != INF) {
        table[i][vertexes+1] = this->min(table[i][vertexes+1],table[i][j]);
      }
    }
  }
  for(j=1;j<=vertexes;++j)
    table[vertexes+1][vertexes+1] += table[j][vertexes+1]; //Sum min cost
  //The same actions as above with the columns:
  for(i=1;i<=vertexes;++i) {
    for(j=1;j<=vertexes,table[j][i]==INF;++j) {};
    table[vertexes+1][i] = table[j][i];
    for(;j<=vertexes;++j) {
      if (table[j][i] != INF) {
        table[vertexes+1][i] = 
          this->min(table[vertexes+1][i],table[j][i]-table[j][vertexes+1]);
      }
    }
  }
  for(j=1;j<=vertexes;++j)
    table[vertexes+1][vertexes+1] += table[vertexes+1][j];
  
} 
  
void Table::Normalize() {
  int i,j;

  CountAgregateCosts();
  for(i = 1; i <= vertexes; ++i)
    for(j = 1; j <= vertexes; ++j)
      if (table[i][j] != INF)
        table[i][j] -= (table[i][vertexes+1]+table[vertexes+1][i]); 
}

double Table::GetMissingCost(int start, int finish) {
  int temp;

  temp = table[start][finish];
  table[start][finish] = INF;
  CountAgregateCosts();
  table[start][finish] = temp;
  return table[vertexes+1][vertexes+1];
}
